package org.lintcode_Pattern;

import java.util.ArrayList;

/**
 * @Auther: qingle
 * @Date: 2024/8/20-22:36
 * @Description:
 * 使用条件
 * • 滑动窗口 (90%)
 * • 时间复杂度要求 O(n) (80%是双指针)
 * • 要求原地操作，只可以使用交换，不能使用额外空间 (80%)
 * • 有子数组 subarray /子字符串 substring 的关键词 (50%)
 * • 有回文 Palindrome 关键词(50%)
 *
 * 复杂度
 * • 时间复杂度：O(n)
 * ￮ 时间复杂度与最内层循环主体的执行次数有关
 * ￮ 与有多少重循环无关
 * • 空间复杂度：O(1)
 * ￮ 只需要分配两个指针的额外内存
 * 炼码例题
 * • LintCode 1879. 两数之和 VII(同向双指针)
 * • LintCode1712.和相同的二元子数组(相向双指针)
 * • LintCode627. 最长回文串 (背向双指针)
 * • LintCode 64: 合并有序数组
 *
 * partition 方法是快速排序中的关键步骤，它通过相向双指针技术将数组分为两部分，一部分小于基准值，另一部分大于基准值。
 * 背向双指针通常用于检查某个条件，例如字符串的回文检查。
 * 同向双指针则用于处理数组或字符串中的连续子序列问题，例如判断子串是否为另一个子串的子序列。
 * 合并双指针则常用于合并两个排序列表，或者在两个数组中找到第k小的元素。
 *
 * @version: 1.0
 */
public class A2双指针 {

	// 1.相向双指针（partition in quicksort）
	public void partition(int[] A, int start, int end) {
		if (start >= end) {
			return;
		}
		int left = start, right = end;
		int pivot = A[(start + end) / 2];
		while (left <= right) {
			while (left <= right && A[left] < pivot) {
				left++;
			}
			while (left <= right && A[right] > pivot) {
				right--;
			}
			if (left <= right) {
				int temp = A[left];
				A[left] = A[right];
				A[right] = temp;
				left++;
				right--;
			}
		}
	}

	// 2.背向双指针
//	int left = position;
//	int right = position + 1;
//	while (left >= 0 && right < length) {
//		if (canStop()) {
//			break;
//		}
//		left--;
//		right++;
//	}

	// 3.同向双指针
//	int j = 0;
//	for (int i = 0; i < n; i++) {
//		while (j < n && !isConditionMet(i, j)) {
//			j++;
//		}
//		if (isConditionMet(i, j)) {
//			processPair(i, j);
//		}
//	}


	// 4.合并双指针
	public ArrayList<Integer> merge(ArrayList<Integer> list1, ArrayList<Integer> list2) {
		ArrayList<Integer> newList = new ArrayList<Integer>();
		int i = 0, j = 0;
		while (i < list1.size() && j < list2.size()) {
			if (list1.get(i) < list2.get(j)) {
				newList.add(list1.get(i));
				i++;
			} else {
				newList.add(list2.get(j));
				j++;
			}
		}
		while (i < list1.size()) {
			newList.add(list1.get(i));
			i++;
		}
		while (j < list2.size()) {
			newList.add(list2.get(j));
			j++;
		}
		return newList;
	}


}
